Efficient Hardware Architectures for BCH Product Codes

QR codes traditionally use 1-D rastered Reed Solomon codes, which can be performance-limited when errors occur along rows and columns. Product codes have potential use in such applications. We designed efficient encoding and decoding hardware architectures for (n, k), t-error correcting BCH product codes in the frequency domain. Using the properties of conjugate classes over a finite field, we reduced the algorithmic complexity of the encoder, leading to a significant reduction in the hardware complexity. A low latency decoder for the above encoder was also designed.

  • A. Mondal and S. S. Garani, "Efficient Hardware Design Architectures for BCH Product Codes in the Frequency Domain", in IEEE Intl. Midwest Symp. on Circuits and Syst. (MWSCAS), 2020, pp. 703-706.


Efficient Hardware Architectures for 2D BCH Codes

In TDMR channels, native 2-D signal processing and coding techniques are required to overcome ISI and noise leading to 2-D burst and random errors. We designed fast and efficient hardware architectures for a 2-D BCH code of size n x n, with a quasi-cyclic burst error correction capability of t x t, in the frequency domain for data storage applications. A fully parallel encoder with the ability to produce an output every clock cycle was designed. Using conjugate class properties of finite fields, the algorithmic complexity of the encoder was significantly reduced. We also designed a pipelined, low-latency decoder for the above encoder. The algorithmic complexity of various pipeline stages of the decoder was reduced significantly using finite field properties, reducing the space complexity of the entire decoder.

  • A. Mondal and S. S. Garani, "Efficient Hardware Architectures for 2-D BCH Codes in the Frequency Domain for Two-Dimensional Data Storage Applications", in IEEE Trans. on Magn., vol. 57, no. 5, pp. 1-14, May 2021, Art no. 3101214.


Deeper Cross-Layer Optimization for Dense NAND SSD

There is a need for a deeper cross-layer optimization for dense NAND SSD to improve read performance of big data applications.
In the case of dense NAND flash such as TLC or QLC, the LSB, CSB and MSB pages in a wordline can be combined to form a larger logical page called melded-page. We have proposed melding TLC/QLC pages to improve the performance of SSD by mitigating the overheads involved in the read operation. Melded-pages are read in their entirety. The controller schedules the write requests in such a way that, during reads later, requests for data present in LSB, CSB and MSB pages are guaranteed to be present in the request queue. This method works reliably when the workload performs its read operations in large chunks or has a predictable I/O pattern. We obtain performance improvements of up to 45% on workloads that use large block sizes such as the Hadoop Distributed File System (HDFS). Big data solutions that exhibit such read patterns can vastly benefit from melding pages.


CLAY CODES

With the current explosion in the volume of data stored in large-scale data centers, running into hundreds of petabytes, ensuring reliable and efficient storage of data calls for a new class of erasure codes. While classical erasure codes such as Reed-Solomon codes are efficient with respect to storage overhead, they are relatively inefficient in terms of handling the repair of a single failed node or storage unit. The coupled-layer (CLAY) codes described in [1,4] are optimal in four respects: they simultaneously minimize (a) the storage overhead, (b) the size of the vector alphabet [5], (c) the amount of data downloaded for repair of a failed node, and (d) the amount of data read from each helper node during node repair. Not surprisingly, the Clay code has attracted the attention of industries that rely upon large-scale data storage including Aricent, Huawei, Salesforce and Uber.
Apart from being one of two teams [2,3] to independently discover the Clay code, our group, in collaboration with storage industry leader NetApp, has been successful in making Clay codes available as an erasure coding option in the recent Nautilus release of the open-source, distributed storage-system Ceph.

  • M. Vajha, V. Ramkumar, B. Puranik, G. R. Kini, E. Lobo, B. Sasidharan, P. V. Kumar: A. Barg, M. Ye, S. Narayanamurthy, S. Hussain, and S. Nandi, Clay codes: Moulding MDS codes to yield an MSR code, USENIX, FAST, 2018, pp. 139–154.
  • M. Ye, A. Barg: Explicit constructions of optimal-access MDS codes with nearly optimal sub-packetization, IEEE Trans Inf Theory, 2017, 63: 6307–6317.
  • B. Sasidharan, M. Vajha, P. V. Kumar: An explicit, coupled-layer construction of a high-rate MSR code with low sub-packetization level, small field size and all-node repair, 2016. ArXiv:1607.07335.
  • S. B. Balaji, M. N. Krishnan, M. Vajha, V. Ramkumar, B. Sasidharan, P. V. Kumar: Erasure Coding for Distributed Storage: An Overview, SCIS, 2018.
  • S. B. Balaji and P. V. Kumar: A tight lower bound on the sub-packetization level of optimal-access MSR and MDS codes, ISIT 2018.
  • Clay plugin in Ceph Nautilus (https://docs.ceph.com/docs/nautilus/rados/operations/erasure-code-clay/)

SECURE DNA BASED COMMUNICATION

As part of our work, a secret message is encoded into 4-ary sequences which are stored in DNA molecules. DNA molecules are long sequences of nucleotides. Customized DNA molecules of short length (roughly 350 nucleotides) can be synthesized if they meet certain constraints. The design of such sequences is hence a constrained-coding problem. The original message is now in the form of distinct DNA molecules and each of them exists in a large number of copies in a small oligo pool. The pool is contained in a very small vial and can be handed over to the intended recipient who can decode the original message by sequencing or reading the DNA molecules.
In this project, we study the errors induced in such a synthesis/storage/sequencing process. We also try to characterize the extent to which DNA molecules are sequenced, by varying the copy number of the information-containing molecules in the pool and by contaminating the pool with some background DNA molecules.
Even at low dilution levels, the authorized recipient would be able to amplify the copy number of molecules with the knowledge of primers and thus decode the message. However, the unauthorized parties who get hold of the vial by some means would not be able to do so at sufficiently lower dilution levels.




Modeling, Capacity and Coding for Granular Magnetic Media

Conventional magnetic recording media are composed of fundamental magnetizable units, called “grains”, that do not have a fixed size or shape. Information is stored on the medium through a write mechanism that sets the magnetic polarities of the grains. The random and unknown underlying distribution of grains causes the bits that actually get written on the medium to be somewhat different from the bits that were intended to be written. In our work, we consider various models, probabilistic as well as combinatorial, for this write channel, and analyze the fundamental limit (capacity) of reliable storage within each model. We also propose coding schemes for reliable storage, with an aim to bridging the gap between capacity upper bounds and achievable coding rates (capacity lower bounds). Another aspect of our work involves the development of sampling algorithms for generating random granular media drawn from some underlying probability distribution on grains. Such algorithms are useful for the purpose of simulating random granular media.



Capacity Computation and Coding for Finite-State Channels

Storage and optical recording media such as magnetic disks, hard drives, CDs, and DVDs are channels with finite memory (or finite-state channels). While multi-letter expressions for the capacities of such channels are known, explicit computations of the capacity as a function of the channel parameters is still an open problem for several simple channel models. Furthermore, there is a need to derive good coding schemes for these channels with state. Our work has been largely motivated by these problems. For the special class of memoryless channels whose inputs must satisfy a no-consecutive-ones constraint, we have derived simple expressions for the feedback capacity and have developed simple coding schemes, based on the principle of posterior matching, that achieve the feedback capacity. We have also considered, in specific, the binary erasure channel (BEC) with more general input-constraints, which mitigate inter-symbol interference and prevent synchronization errors, and have derived good bounds on both the feedback and non-feedback capacities. Our present work is concerned with exploring codes with low complexity encoding and decoding procedures that achieve good rates over the input-constrained BEC without feedback.



CODES FOR DISTRIBUTED STORAGE

To ensure reliability within a data center, information pertaining to a file is stored in distributed and redundant fashion across a network of storage nodes.   The amount of data housed can run into the petabytes, thereby causing the industry to increasingly turn towards erasure-correcting codes to ensure that this reliability comes with the smallest possible storage overhead.   Given that the the failure of an individual storage unit is a common occurrence, the need IS for erasure-coding techniques that are efficient in dealing with node failure as well.   In part response to this challenge, coding theorists have come up with two new classes of codes, namely Regenerating Codes and Codes with Locality.   Our group has been a string contributor to the development of the theory of both regenerating codes as well as codes with locality in terms of providing construction of optimal codes and the development of fundamental limits.



TWO-DIMENSIONAL MAGNETIC STORAGE

TDMR channels achieve high recording densities by reducing the size of bits to the order of size of the magnetic grains on the medium. The effects of the random distribution of grains on the medium become more pronounced, resulting in jitter noise. At low recording densities, the jitter noise can be modeled as a first order variation of the channel response. At high recording densities, a mode accurate channel model including the randomness in the grain positions has is being used. Our group has been a world leader in all aspects of TDMR channels engineering that includes, 2D PR equalization using separable and non-separable targets, timing recovery, 2D signal detection techniques using iterative techniques, 2D ECCs including LDPC and algebraic codes.



3D-NAND FLASH

3D NAND flash is has memory cells are stacked vertically in multiple layers, providing higher capacity at increased manufacturing costs. Unlike magnetic storage, the channels engineering aspects in 3D flash is entirely digital requiring detectors and powerful multidimensional codes to work with these systems Our group has contributed to the state-of-the-art codes that work with NAND flash with the best-in-class LDPC and BCH codes with high level of performance in reliability and hardware requirements.



Volume holographic recording

Volume holographic recording is an archival type storage. The advantages with VHMs include high capacity, high throughput and parallel data access using non-inertial optical beams, rotatory aspects. From a channels engineering perspective, we need powerful multidimensional signal processing and codes to work with these systems. Our group has significantly contributed to signal detection, 2D non-binary modulation codes, 2D ECCS and information-theoretic limits for holographic channels.



VLSI CIRCUITS AND SYSTEMS ASPECTS FOR DATA STORAGE

On the architectural side, it is important to realize algorithms that are aware of the physical constraints such as throughput, area, power and leakage. Realization of VLSI architectures that are amenable to a system-on-chip (SoC) is valuable for advancement of channels technology to practice Our group has significantly contributed to the development of binary LDPC encoders/layered and non-layered decoders, Reed Solomon decoders, synchronous and asynchronous 1D SOVA detector, 2D separable SOVA detector, timing recovery circuits etc. that work with perpendicular recording, TDMR and 3D-NAND flash.